package com.lfg.leetcode.leetcode0;


import java.util.HashMap;
import java.util.Map;

public class No37SolveSudoku {


    public static void main(String[] args) {

        char[][] array = new char[9][9];
//        array[0] = new char[]{'5','3','4','6','7','8','9','1','2'};
//        array[1] = new char[]{'6','.','.','1','9','5','.','.','.'};
//        array[2] = new char[]{'.','9','8','.','.','.','.','6','.'};
//        array[3] = new char[]{'8','.','.','.','6','.','.','.','3'};
//        array[4] = new char[]{'4','.','.','8','.','3','.','.','1'};
//        array[5] = new char[]{'7','.','.','.','2','.','.','.','6'};
//        array[6] = new char[]{'.','6','.','.','.','.','2','8','.'};
//        array[7] = new char[]{'.','.','.','4','1','9','.','.','5'};
//        array[8] = new char[]{'.','.','.','.','8','.','.','7','9'};


//        array[0] = new char[]{'5','3','4','6','7','8','9','1','2'};
//        array[1] = new char[]{'6','7','2','1','9','5','3','4','8'};
//        array[2] = new char[]{'1','9','8','3','4','2','5','6','7'};
//        array[3] = new char[]{'8','5','9','7','6','1','4','2','3'};
//        array[4] = new char[]{'4','2','6','8','5','3','7','9','1'};
//        array[5] = new char[]{'7','1','3','9','2','4','8','5','6'};
//        array[6] = new char[]{'9','6','1','5','3','7','2','8','4'};
//        array[7] = new char[]{'2','8','7','4','1','9','6','3','5'};
//        array[8] = new char[]{'3','4','5','2','8','6','1','7','.'};

        array[0] = new char[]{'5', '1', '9', '7', '4', '8', '6', '3', '2'};
        array[1] = new char[]{'7', '8', '3', '6', '5', '2', '4', '1', '9'};
        array[2] = new char[]{'4', '2', '6', '1', '3', '9', '8', '7', '5'};
        array[3] = new char[]{'3', '5', '7', '9', '8', '6', '2', '4', '1'};
        array[4] = new char[]{'2', '6', '4', '3', '1', '7', '5', '9', '8'};
        array[5] = new char[]{'1', '9', '8', '5', '2', '4', '3', '6', '7'};
        array[6] = new char[]{'9', '7', '5', '8', '6', '3', '1', '2', '4'};
        array[7] = new char[]{'8', '3', '2', '4', '9', '1', '7', '5', '6'};
        array[8] = new char[]{'6', '4', '1', '2', '7', '5', '9', '8', '.'};

//        array[0] = new char[]{'.', '.', '9', '7', '4', '8', '.', '.', '.'};
//        array[1] = new char[]{'7', '.', '.', '.', '.', '.', '.', '.', '.'};
//        array[2] = new char[]{'.', '2', '.', '1', '.', '9', '.', '.', '.'};
//        array[3] = new char[]{'.', '.', '7', '.', '.', '.', '2', '4', '.'};
//        array[4] = new char[]{'.', '6', '4', '.', '1', '.', '5', '9', '.'};
//        array[5] = new char[]{'.', '9', '8', '.', '.', '.', '3', '.', '.'};
//        array[6] = new char[]{'.', '.', '.', '8', '.', '3', '.', '2', '.'};
//        array[7] = new char[]{'.', '.', '.', '.', '.', '.', '.', '.', '6'};
//        array[8] = new char[]{'.', '.', '.', '2', '7', '5', '9', '.', '.'};

        solveSudoku(array);
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void solveSudoku(char[][] board) {
        if (!isValidSudoku(board)) {
            return;
        }
        solveSudoku(board, 0, 0);
    }

    public static boolean solveSudoku(char[][] board, int i, int j) {

        if (i >= board.length - 1 && j >= board[0].length) {
            return true;
        }
        for (; i < board.length; i++) {
            if (j > 8) {
                j = 0;
            }
            for (; j < board[i].length; j++) {
                char c = board[i][j];
                if ('.' != c) {
                    continue;
                }
                for (char n = '1'; n <= '9'; n++) {
                    board[i][j] = n;
                    if (!isValidSudoku(board, i, j)) {
                        board[i][j] = '.';
                        continue;
                    }
                    if (solveSudoku(board, i, j + 1)) {
                        return true;
                    }
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }

    public static boolean isValidSudoku(char[][] board, int i, int j) {
        int a = i / 3 * 3;
        int b = j / 3 * 3;
        Integer[] rows = new Integer[9];
        Integer[] columns = new Integer[9];
        Integer[] middle = new Integer[9];
        for (int n = 0; n < 9; n++) {
            int i1 = board[i][n] - '1';
            if (i1 >= 0 && rows[i1] != null) {
                return false;
            }
            int i2 = board[n][j] - '1';
            if (i2 >= 0 && columns[i2] != null) {
                return false;
            }
            if (i1 >= 0) {
                rows[i1] = 1;
            }
            if (i2 >= 0) {
                columns[i2] = 1;
            }

        }
        for (int n = 0; n < 3; n++) {
            for (int m = 0; m < 3; m++) {
                int i1 = board[a + n][b + m] - '1';
                if (i1 >= 0 && middle[i1] != null) {
                    return false;
                }
                if (i1 >= 0) {
                    middle[i1] = 1;
                }
            }
        }
        return true;
    }

    public static boolean isValidSudoku(char[][] board) {
        Map<String, Integer[]> data = new HashMap<String, Integer[]>();

        for (int i = 0; i < board.length; i++) {
            Integer[] rows = new Integer[9];
            for (int j = 0; j < board[i].length; j++) {
                int num = board[i][j];
                if (46 == num) {
                    continue;
                }
                num = num - 49;
                if (num < 0 || num > 9) {
                    return false;
                }
                String ckey = "c_" + j;
                Integer[] columns = data.getOrDefault(ckey, new Integer[9]);
                if (columns[num] != null) {
                    return false;
                }
                if (rows[num] != null) {
                    return false;
                }
                String mkey = String.valueOf(i / 3) + '_' + j / 3;
                Integer[] middle = data.getOrDefault(mkey, new Integer[9]);
                if (middle[num] != null) {
                    return false;
                }
                rows[num] = num;
                columns[num] = num;
                middle[num] = num;
                data.put(mkey, middle);
                data.put(ckey, columns);
            }
        }
        return true;
    }
}

